This invention relates to the compression of two-dimensional black/white pictures normally coded as a p.times. q array of two-valued sample points and, more particularly, to improvements in the compression of such images using predictive/variable-length encoding techniques.
It is well appreciated that run-length encoding of black and white sequences could be performed directly on the Boolean values of the sample points or picture elements ("pels") constituting a two-dimensional array representative of the image taken in row major order. In general, run-length encoding can be thought of as a form of "relative addressing" occasioned by the use of an index plus relative count. Passing the image into runs is accompanied by variable length encoding of each run with an independent codeword. The compressed size of an image is then the product of the number of codewords (runs) and the average codeword length.
The question arises as to what effect, if any, would there be upon run-length encoding if the distribution of runlengths of blackness or whiteness of two-dimensional encoded arrays representative of the original picture could be altered. Assuming black data on white background, consider that a page of alphanumeric text consists of approximately 90% white pels and 10% black pels. When such a page of text is scanned in row major order, i.e., consecutive raster scan lines, one counts a large number of white pels and very few black pels. The distribution of run-lengths of black typically peak at around a length of 2, whereas the distribution for white runs typically peaks at around a run-length of 15. In contrast, the complement or "negative" image of the same page of alphanumeric text will have approximately 90% blackness and 10% whiteness. Furthermore, the position of the peaks in its run-length distributions will have reversed to typically 15 and 2, respectively. Similarly, changes in sampling resolution for a given graphic image cause significant changes in the run-length distributions. For black text on a white background, the peak in black run-length distribution represents the average stroke width in the type on the page. This peak will shift as you change the sampling interval. Optimal coding of this kind of data requires run counting and encoding of black and white sequences separately and, perhaps, adaptively. It would simplify run-length encoding if one could "bleach out" some of the blackness so that all transformed image arrays would contain only a few black pels with adjacent black pel pairs as a near-rare event. Then, one would really have to only run-length encode sequences of white pels by implicitly assuming the existence of one black pel at the end of each run. Consecutive black pels could be represented as white pel runs of length zero. This method eliminates the need for separate variable-length encoders for black and white runs. It also halves the number of runs to encode by essentially eliminating the encoding of black runs. If the reduction in blackness is accomplished without doubling the number of white/black run pairs, then the above "rare-event" coding results in an overall reduction in the number of codewords per image and thereby the compressed image size as well. Such a process of "bleaching out" in an image can be achieved by the process called "predictive encoding".
Predictive coding according to J. S. Wholey, "The Coding of Pictorial Data", IRE Transactions on Information Theory, April 1961, pages 99-102, involves a multi-step process. It is based upon the ability to predict the black or white value of the next pel in any given scan line based upon the black or white cluster of pels in neighboring positions usually in the same or immediately preceding scan lines. What then is actually encoded is only the non-correspondence between the predicted and actual pel value. Now, as a predictor takes into account more "past history", then the accuracy of the predictions should improve (although with diminishing incremental effectiveness). This means that a number of neighboring pels in the same and previous scan lines would be used to predict the pel values. A predictor using only the j- 1 pel value for predicting the value of the jth pel would be spoken of as a "first-order" predictor. A third order predictor might consist of the j- 1 pel value for the ith scan line and the j- 1 and jth pel for the ith- 1 scan line. A third order predictor thus consists of a cluster of three neighboring pels with 2.sup.3 or eight different states in order to obtain a prediction function, that is, a table in which each of the possible 3-pel states predicts the pel value (black/white) which is most likely to follow it. In contrast, a single-order predictor can only predict based upon two possible states. The effect of serially applying the pq Boolean values of a p.times. q array of two-valued sample points in row major order to a predictor is to transform the matrix into another p.times. q matrix in which each point represents correspondence or non-correspondence between the actual and predicted values. Typically, 1 represents noncorrespondence or error between the values and 0 represents correspondence or no-error. Thus, the array generated by a higher-order predictor would have a smaller percentage of 1's (blackness) than a low-order predictor. Note that this transformation is a 1:1 mapping and results in no data compression of itself. However, it less than doubles the number of white/black run pairs as well as reduces the overall blackness and, hence, corresponds to the aforementioned "bleaching". The run-length encoding of runs of whites or 0's between the occurrence of 1's in the "error matrix" is described by Wholey in his article and by Arps in U.S. Pat. No. 3,813,485, issued May 28, 1974. This is characterized as predictive/run-length encoding. As described by Arps, exhaustive, non-causal predictive encoding looks at adjacent points on previous lines and preceding points of the present line in order to predict for all possible states the two-level value of the next pel. If the prediction is in error, a binary 1 is transmitted. Alternatively, if the prediction is correct, a binary 0 is transmitted. Run-length coding is used to specify the run-lengths of binary 0 non-errors and thereby to implicitly locate their accompanying binary 1 errors. Restated, the coding process boils down to describing where binary 1 errors occur; and one initiates a run count based on the occurrence of an error indication from the predictive encoder, continuing the count of non-errors until the next error output is encountered.
The most pertinent prior art is set forth in H. E. White et al in an article entitled, "Dictionary Lookup Encoding of Graphics Data" appearing in the anthology by T. S. Huang and O. J. Tretiak, Picture Bandwidth Compression, Gordon and Breach Science Publishers, New York, 1972, LC74-135062, 1972, at pages 267-281. This article proposes to increase the compression obtained by first-order predictive/run-legnth encoding of a two-valued image by the addition of an alternative coding method called "reference coding". In this method, 1-pel prediction errors are coded whenever possible by locating them with respect to nearby 1-pel prediction errors in the immediately previous line (rather than by locating them with respect to the immediately preceeding error in the present line as with run-length coding). Three reference codewords are defined, specifying error locations below a previous line prediction error as directly below or one pel to the left or right from directly below. Note that "reference coding" is not always possible and that run-length coding must be used as a backup for combinations that it cannot handle (such as prediction errors without nearby errors available in the preceding line).